package leetcode.周赛.第249场;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/7/11 14:33
 * @description：https://leetcode-cn.com/contest/weekly-contest-249/problems/merge-bsts-to-create-single-bst/
 */
public class 合并多棵二叉搜索树 {
    @Test
    public void test() {
        Solution solution = new Solution();
        List<TreeNode> trees = new ArrayList<>();
        trees.add(new TreeNode(2, new TreeNode(1), new TreeNode(3)));
        trees.add(new TreeNode(3, new TreeNode(2), null));
        //trees.add(new TreeNode(5, new TreeNode(4), null));
        TreeNode treeNode = solution.canMerge(trees);
        infixOrder(treeNode);

    }


     //Definition for a binary tree node.
     public class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode() {}
         TreeNode(int val) { this.val = val; }
         TreeNode(int val, TreeNode left, TreeNode right) {
             this.val = val;
             this.left = left;
             this.right = right;
         }

         @Override
         public String toString() {
             return "TreeNode{" +
                     "val=" + val +
                     ", left=" + left +
                     ", right=" + right +
                     '}';

         }
     }

    public void infixOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.println(node.val);
        infixOrder(node.left);
        infixOrder(node.right);
    }


    class Solution {
        Map<Integer, TreeNode> map = new HashMap<>();

        List<Integer> list = new ArrayList<Integer>();

        public TreeNode canMerge(List<TreeNode> trees) {
            for (TreeNode tree : trees) {
                map.put(tree.val, tree);
            }
            int preSize = 0;
            while (trees.size() > 1) {
                if (trees.size() == preSize) {
                    return null;
                } else {
                    preSize = trees.size();
                }
                for (TreeNode tree : trees) {
                    if (map.containsKey(tree.val)) {
                        dfs(tree, map);
                    }
                }
                trees = new ArrayList<>();
                for (Map.Entry<Integer, TreeNode> entry : map.entrySet()) {
                    trees.add(entry.getValue());
                }
            }
            if (trees.size() == 0) return null;
            infixOrder(trees.get(0));
            for (int i = 0; i < list.size() - 1; i++) {
                if (list.get(i) > list.get(i + 1)) return null;
            }
            return trees.get(0);
        }

        public void dfs(TreeNode node, Map<Integer, TreeNode> map) {
            HashMap<Integer, TreeNode> curMap = new HashMap<>(map);
            curMap.remove(node.val);
            if (node.left != null) {
                int leftVal = node.left.val;
                TreeNode left = curMap.get(leftVal);
                if (left != null) {
                    node.left = left;
                    curMap.remove(leftVal);
                    this.map.remove(leftVal);
                    dfs(left, curMap);
                }
            }
            if (node.right != null) {
                int rightVal = node.right.val;
                TreeNode right = curMap.get(rightVal);
                if (right != null) {
                    node.right = right;
                    curMap.remove(rightVal);
                    this.map.remove(rightVal);
                    dfs(right, curMap);
                }
            }
        }

        public void infixOrder(TreeNode node) {
            if (node == null) {
                return;
            }
            infixOrder(node.left);
            list.add(node.val);
            infixOrder(node.right);
        }
    }

}
